The invention is in the field of information processing. Specifically, the invention relates to the detection of overflow in residue number system (RNS) multiplication operations.
The RNS has received considerable attention in recent times as an effective tool for performing single step, parallel computation of sums, differences, and products. A system employing the RNS may be used for high speed, real time, parallel processing of data.
A difficulty associated with actually achieving fast computation with the RNS is that a RNS representation of a number does not provide explicit sign and magnitude information. The lack of explicit sign and magnitude information hinders overflow detection. Residue Arithmetic and Its Application to Computer Technology, N.S. Szabo and R.I. Tanaka, (McGraw Hill, New York, 1967), and "Residue Arithmetic: A Tutorial with Examples," F.J. Taylor Computer Vol. 17, No. 5, pp. 50-62 (May 1984), both incorporated by reference, provide general background information on the RNS and the mixed base number system, to be discussed below.
Optical information processors which are ideally suited to perform the parallel computations required in RNS arithmetic are currently under development. There are fundamental differences between optical processors based on optical circuits in which the information carriers are photons and electronic processors based on electronic circuits in which the information carriers are electrons. In optical circuits the photon carriers do not interact with one another, while in electronic circuits the electron carriers do interact with one another. This fact means that in optical circuits interconnect possibilities exist that do not exist with electronic circuits. In particular, optical circuits allow parallel architectures which perform arithmetic and logical operations in completely parallel, single step processes. Since the speed of optical devices is essentially limited to the time it takes for a photon to transit a device, no faster computation time is possible.
The capability to detect overflow is a fundamental requirement of any general purpose computer whether the computer is optical or electronic. A slow overflow detection system slows the speed of the entire computational process. Thus, in order to provide an efficient optical processor based on RNS arithmetic, it is desirable to develop an RNS overflow detection capability which does not rely on explicit sign and magnitude information.
U.S. Pat. No. 4,121,298 entitled "Central Processing Unit for Numbers Represented in the System of Residual Classes," issued to Akushsky et al, discloses a RNS computer which detects overflow via a position attribute, or core function. Use of the core function has the disadvantage that the core function is not necessarily monotonically increasing and therefore can produce somewhat ambiguous magnitude results. The invention disclosed in the '298 patent also requires time consuming feedback and iteration. In addition, a time consuming sequential division algorithm is employed in the '298 patent. Since the sequential division algorithm does not have a fixed length, the '298 system can not be used in conjunction with a pipelined system. The '298 patent is not designed to be used in conjunction with optical circuitry. Thus, the '298 device is not suitable for use for overflow detection in a high speed optical computer.
U.S. Pat. No. 4,064,400 entitled "Device For Multiplying Numbers in a System of Residual Classes," issued to Akushsky et al discloses a fully electronic RNS multiplier which detects overflow resulting from multiplication. The device disclosed in the '400 patent operates internally in binary. The multiplier is converted from its RNS representation to a binary fraction and an order of magnitude indicator is used for overflow detection. The binary fraction bits are used serially to perform Russian Multiplication Theorem operations on the multiplicand using RNS arithmetic. The serial use of the binary fraction bits in the '400 patent is time consuming. In addition, the magnitude indicator used in the '400 patent has disadvantages similar to those described above with respect to the core function used in the '298 patent. The electronic circuits employed by the device disclosed in the '400 patent are slower than optical circuits. Thus, the device disclosed in the '400 patent could not be used in an optical computer without significantly decreasing the overall speed of the optical computer.
Accordingly, there is a need for a high speed RNS multiplication overflow detection processor which can be effectively used in an optical computer.